package algorithm_optimal_solution.LinkedList;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

//环形单链表的约瑟夫问题：在环中。两个节点，lastNode指向头节点，headNode指向第二个节点，当符合条件时，lastNode的下一个指向headNode的下一个。
//每删除一个节点遍历m次，共需删除n-1个节点，时间复杂度为O(n*m)

//还有一种解法只需要花费O(n)时间，递归解法，老编号 = （新编号 + 报数）% i + 1
public class RingJosephus {

    static class Node{
        private int value;
        private Node node;

        public Node(int value,Node node){
            this.value = value;
            this.node = node;
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public Node getNode() {
            return node;
        }

        public void setNode(Node node){
            this.node = node;
        }
    }

    /*public void ringJosephus(Node head,int number){
        int index = 1;
        int count = 1;
        Node pre = null;
        Node node = head;
        while(head.getNode() != null){
            if(count % number == 0){
                if(index == 1){
                    head = head.getNode();
                    node = node.getNode();
                    index++;
                    count++;
                    pre = node;
                    continue;
                }else if(node.getNode() == null){
                    pre.setNode(null);
                }else{
                    pre.setNode(node.getNode());
                }
            }
            pre = node;
            if(node.getNode() == null){
                index = 1;
                node = head;
            }else{
                index++;
                node = node.getNode();
            }
            count++;
        }
        System.out.print(head.getValue());
    }*/

    public void ringJosephus(Node head,int number){
        Node last = head;
        while(last.getNode() != head){
            last = last.getNode();
        }
        int count = 0;
        while(last != head){
            if(++count == number){
                last.setNode(head.getNode());
                count = 0;
            }else{
                last = last.getNode();
            }
            head = head.getNode();
        }
        System.out.print(head.getValue());
    }

    public void ringJosephusQuick(Node head,int number){
        if(head == null || head.getNode() == head || number < 1){
            System.out.println(head);
            return;
        }
        Node next = head.getNode();
        int count = 1;
        while(next != head){
            count++;
            next = next.getNode();
        }
        count = getLive(count,number);
        while(--count != 0){
            head = head.getNode();
        }
        head.setNode(head);
        System.out.println(head.getValue());
    }

    private int getLive(int i,int number){
        if(i == 1){
            return 1;
        }
        return (getLive(i - 1,number) + number - 1) % i + 1;
    }

    public static void main(String[] args)throws IOException {
        BufferedReader scanner = new BufferedReader(new InputStreamReader(System.in));
        String[] numbers = scanner.readLine().split(" ");
        int len = Integer.parseInt(numbers[0]);
        int number = Integer.parseInt(numbers[1]);
        Node node = new Node(len,null);//环形单链表
        Node currentNode = node;
        for(int i = len - 1;i > 0;i--){
            node = new Node(i,node);
        }
        currentNode.setNode(node);
//        new RingJosephus().ringJosephus(node,number);
        new RingJosephus().ringJosephusQuick(node,number);
    }
}
